package study;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class InsertInterval {
    public static int[][] insertInterval(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            intervals[0] = newInterval;
            return intervals;
        }
        int head = newInterval[0];
        int tail = newInterval[1];
        int flag = 0;
        int local = 0;
        int left = 0;
        int right = intervals.length - 1;
        for (int i = left; i < right + 1; i++) {
            if (intervals[i][1] < head) {
                if (tail < intervals[i + 1][0]) {
                    local = i;
                    flag = 1;
                    break;
                }
                left = (left + right) / 2 - 1;
                i = left - 1;
            } else if (intervals[i][1] >= head && head > intervals[i][0]) {
                if (intervals[i + 1][0] <= tail) {
                    intervals[i][1] = intervals[i + 1][1];
                    flag = -1;
                    for (int j = i + 2; j < right; j++) {
                        if (intervals[j][0] <= tail) {
                            flag--;
                            intervals[i][1] = intervals[j][1];
                        }
                    }
                    break;
                } else {
                    intervals[i][1] = tail;
                    flag = 0;
                }
                local = i;
                break;
            } else if (head < intervals[i][0]) {
                right = (left + right) / 2 + 1;
                i = left - 1;
            }
        }
        int length = intervals.length;
        if (flag < 0) {
            length = length + flag;
        }
        if (flag == 1) {
            length = length + 1;
        }
        int[][] ret = new int[length][2];
        for (int i = 0; i < length; i++) {
            if (flag == 1) {
                if (i <= local) {
                    ret[i] = intervals[i];
                } else if (i == local + 1) {
                    ret[i] = newInterval;
                } else {
                    ret[i] = intervals[i - 1];
                }
            } else if (flag == 0) {
                ret[i] = intervals[i];
            } else {
                if (i <= local + 1) {
                    ret[i] = intervals[i];
                } else {
                    ret[i] = intervals[i - flag];
                }
            }
        }
        return ret;
    }

    // 对拍
    public static int[][] insertInterval2(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            intervals[0] = newInterval;
            return intervals;
        }
        List<int[]> temp = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int[] inter = intervals[i];
            if (inter[1] < newInterval[0]) {
                temp.add(inter);
                continue;
            }
            if (inter[0] > newInterval[1]) {
                temp.add(inter);
                continue;
            }
            if (i < intervals.length - 1 && intervals[i + 1][0] > newInterval[1]) {
                temp.add(newInterval);
                continue;
            }
            if (inter[0] <= newInterval[0]) {
                if (inter[1] >= newInterval[1]) {
                    temp.add(inter);
                    continue;
                } else {
                    if (newInterval[1] < intervals[i + 1][0]) {
                        inter[1] = newInterval[1];
                        temp.add(inter);
                        continue;
                    } else {
                        for (int j = i + 1; j < intervals.length; j++) {
                            if (newInterval[1] >= intervals[j][0] && newInterval[1] <= intervals[j][1]) {
                                inter[1] = intervals[j][1];
                                temp.add(inter);
                                i = j;
                                break;
                            } else if (newInterval[1] > intervals[j][1] && newInterval[1] < intervals[j + 1][0]) {
                                inter[1] = newInterval[1];
                                temp.add(inter);
                                i = j;
                                break;
                            }
                        }
                    }
                }
            }
        }
        int[][] ret = new int[temp.size()][2];
        for (int i = 0; i < temp.size(); ++i) {
            ret[i] = temp.get(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        int[][] input1 = {{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[] input2 = {4, 8};
        int[][] ret1 = insertInterval(input1, input2);
        // 重置测试数据，用于对拍测试
        input1 = new int[][]{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}};
        int[][] ret2 = insertInterval2(input1, input2);
        for (int i = 0; i < ret1.length; i++) {
            System.out.println(Arrays.toString(ret1[i]));
        }
        for (int i = 0; i < ret2.length; i++) {
            System.out.println(Arrays.toString(ret2[i]));
        }
    }
}
